{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -*- coding: gbk -*-\n",
    "def LZW ( inStr,narrow=False,bits=14):\n",
    "    '''使用LZW压缩算法压缩。\n",
    "        narrow为True时输出字节流位紧缩\n",
    "        默认最大位宽14位，允许范围12~16位'''\n",
    "    if isinstance(inStr,str):\n",
    "        inStr=list(inStr)\n",
    "        for i in range(len(inStr)):\n",
    "            inStr[i]=ord(inStr[i])\n",
    "    sOutStr=[256]   #先放一个 开始&清除 标记\n",
    "    mTagMap={}      #字典\n",
    "    iTagCurrent=258  #当前的标记总数 0~255 标记256 为begin & clear , 257 为end\n",
    "    iBitsLen=9\n",
    "\n",
    "    iTag=inStr[0]   #当前标记\n",
    "    ii=0\n",
    "    cTemp=0\n",
    "    if bits>16 or bits<12:\n",
    "        return None\n",
    "    iMaxLen=(1<<bits)-1     #最多允许的标记数，由位宽决定\n",
    "    \n",
    "    for ii in range(1,len(inStr)):\n",
    "        cChar=inStr[ii]\n",
    "        cTemp=(iTag<<8)+cChar   #（前缀 后缀）\n",
    "        if cTemp in mTagMap:    #该（前缀 后缀）已存在\n",
    "            iTag=mTagMap[cTemp] #取出其标记\n",
    "        else:   #不存在\n",
    "            sOutStr.append(iTag) #将前缀放入输出流\n",
    "            mTagMap[cTemp]=iTagCurrent\n",
    "            iTagCurrent+=1      #增加一个标记，并放入字典\n",
    "            iTag=cChar  #当前标记为后缀\n",
    "\n",
    "        if iTagCurrent>=iMaxLen:    #如果到达了最大标记数，清除字典，从头开始\n",
    "            sOutStr.append(256)\n",
    "            mTagMap={}\n",
    "            iTagCurrent=258\n",
    "\n",
    "    if iTag!=0:\n",
    "        sOutStr.append(iTag)\n",
    "    sOutStr.append(257) #放入结束标记\n",
    "    \n",
    "    if narrow:  #位紧缩\n",
    "        return Narrow(sOutStr)\n",
    "    else:\n",
    "        return sOutStr\n",
    "    \n",
    "def Narrow (sOutStr):\n",
    "    sOutN=[]\n",
    "    iTemp=0\n",
    "    BitLeft=0 \n",
    "    nowBit=9 #当前位宽\n",
    "    nowStag=1<<nowBit #当前位宽允许的标记数\n",
    "    nowTagCount=258\n",
    "    for cChar in sOutStr:\n",
    "        iTemp=iTemp+(cChar<<BitLeft)\n",
    "        nowTagCount+=1\n",
    "        BitLeft+=nowBit\n",
    "        \n",
    "        if cChar==256:\n",
    "            nowBit=9\n",
    "            nowStag=1<<nowBit\n",
    "            nowTagCount=258\n",
    "        \n",
    "        if nowTagCount>=nowStag:\n",
    "            nowBit+=1\n",
    "            nowStag=1<<nowBit\n",
    "            \n",
    "        while BitLeft>=8:\n",
    "            sOutN.append(iTemp&0xff)\n",
    "            iTemp=iTemp>>8\n",
    "            BitLeft-=8\n",
    "    if BitLeft>0:\n",
    "        sOutN.append(iTemp)\n",
    "    return sOutN\n",
    "\n",
    "def UnNarrow (inStr):\n",
    "    sOut=[]\n",
    "    iTemp=0\n",
    "    BitLeft=0\n",
    "    nowBit=9\n",
    "    nowStag=1<<nowBit\n",
    "    mask=nowStag-1\n",
    "    nowTagCount=258\n",
    "    for cChar in inStr:\n",
    "        iTemp=iTemp+(cChar<<BitLeft)\n",
    "        BitLeft+=8\n",
    "        if BitLeft>=nowBit:\n",
    "            cTemp=iTemp&mask\n",
    "            iTemp=iTemp>>nowBit\n",
    "            BitLeft-=nowBit\n",
    "            sOut.append(cTemp)\n",
    "            nowTagCount+=1\n",
    "            if nowTagCount>=nowStag:\n",
    "                nowBit+=1\n",
    "                nowStag=1<<nowBit\n",
    "                mask=nowStag-1\n",
    "            if cTemp==256:\n",
    "                nowBit=9\n",
    "                nowStag=1<<nowBit\n",
    "                mask=nowStag-1\n",
    "                nowTagCount=258\n",
    "    if BitLeft>0:\n",
    "        sOut.append(iTemp)\n",
    "\n",
    "    return sOut\n",
    "\n",
    "def deTag ( mTagMap,nowTag,outStr):\n",
    "    '''将一个标记转化为元字符序列，并放入到输出流中'''\n",
    "    if nowTag>=0:\n",
    "        sTemp=[]\n",
    "        while nowTag>255:\n",
    "            pair=mTagMap[nowTag]\n",
    "            sTemp.append(pair[1])\n",
    "            nowTag=pair[0]\n",
    "        sTemp.append(nowTag)\n",
    "        sTemp.reverse()\n",
    "        outStr+=sTemp\n",
    "    return nowTag\n",
    "\n",
    "def UnLZW ( inStr , narrow=False):\n",
    "    if narrow:\n",
    "        inStr=UnNarrow(inStr)\n",
    "    \n",
    "    mTagMap={}\n",
    "    outStr=[]\n",
    "    nowTagCount=258\n",
    "    sTemp=[]\n",
    "    nowTag=-1\n",
    "    for cChar in inStr:\n",
    "        if cChar==256:\n",
    "            if nowTag>=0:\n",
    "                deTag(mTagMap,nowTag,outStr)\n",
    "            mTagMap={}\n",
    "            nowTagCount=258\n",
    "            nowTag=-1\n",
    "        elif cChar==257:\n",
    "            if nowTag>=0:\n",
    "                deTag(mTagMap,nowTag,outStr)\n",
    "                nowTag=-1\n",
    "            return outStr\n",
    "        elif nowTag==-1: #刚开始\n",
    "            nowTag=cChar\n",
    "        else:\n",
    "            pair=[nowTag,0]\n",
    "            mTagMap[nowTagCount]=pair\n",
    "            nowTagCount+=1\n",
    "            surfix=cChar\n",
    "            while surfix>255:\n",
    "                if surfix not in mTagMap:\n",
    "                    print('Thera are errors in input')\n",
    "                    return outStr\n",
    "                surfix=mTagMap[surfix][0]\n",
    "            pair[1]=surfix\n",
    "            deTag(mTagMap,nowTag,outStr)\n",
    "            nowTag=cChar\n",
    "            \n",
    "def fileLZW ( inFile , outFile , bit=14 ):\n",
    "    import os\n",
    "    fsize=os.stat(inFile)[6]\n",
    "    f=os.open(inFile,os.O_BINARY)\n",
    "    s=os.read(f,fsize)\n",
    "    os.close(f)\n",
    "    \n",
    "    a=LZW(s,True,bit)\n",
    "    f=open(outFile,'wb')\n",
    "    outs=''\n",
    "    for i in a:\n",
    "        outs+=chr(i)\n",
    "    f.write(outs)\n",
    "    f.close()\n",
    "\n",
    "def fileUnlzw ( inFile , outFile):\n",
    "    import os\n",
    "    fsize=os.stat(inFile)[6]\n",
    "    f=os.open(inFile,os.O_BINARY)\n",
    "    s=os.read(f,fsize)\n",
    "    a=[]\n",
    "    for i in s:\n",
    "        a.append(ord(i))\n",
    "    b=UnLZW(a,True)\n",
    "    f=open(outFile,'wb')\n",
    "    outs=''\n",
    "    for i in b:\n",
    "        outs+=chr(i)\n",
    "    f.write(outs)\n",
    "    f.close()\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:zhong]",
   "language": "python",
   "name": "conda-env-zhong-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
